package com.ljx.offer;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @author 李捷禧
 * Date: 2023/3/17
 * ClassName: C_39
 */

public class C_39 {
    /**
     *如果相等的数超过一半，就会输出res
     * max会一直不等于零，res不用换值
     * 如果没有相等的数超过一半的，就会在数组几个数中输出一个数
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int res = 0,max = 0;
        for (int num : nums) {
            if(max == 0) res = num;
            max += num == res ? 1 : -1;
        }
        return res;
    }

    /**
     * 超出时间
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        int max = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            if(count > max){
                max = count;
                res = nums[i];
            }
        }
        if (max > (nums.length / 2)) return res;
        else return 0;
    }

    @Test
    public void test(){
        int[] arr = new int[]{ 2, 3, 2,2,2, 2,5, 4,9,5,9,8,7};
        int a = majorityElement(arr);
        System.out.println(a);
    }

}
